#include "base/core/Profiler.h"
#include "base/core/com_define.h"
#include "base/core/log.h"
#include "base/core/os/string.h"
#include "base/core/os/thread.h"
#include "base/core/os/mutex.h"
#include <unordered_map>
#include <set>

#ifdef WIN32
#include <windows.h>
static LARGE_INTEGER gs_Frequence = { 0 };
#endif

struct PROFILER_MANAGER 
{
    unsigned timerCount;
    PROFILE_TIMER* timers[PROFILER_MAX_TIMER_COUNT];

    unsigned stackLevel;
    PROFILE_TIMER* stack[PROFILER_MAX_STACK_LEVEL];

    PROFILER_MANAGER() 
	{
        timerCount = 0;
        stackLevel = 0;
#ifdef WIN32
        QueryPerformanceFrequency(&gs_Frequence);
#endif
    }
};

static PROFILER_MANAGER gs_Profiler;
static THREAD_ID gs_ProfileThreadID = 0;
void BeginProfile(PROFILE_TIMER* timer) 
{
	if (!g_isOpenProfile)
	{
		return;
	}
    if (!timer || (gs_Profiler.stackLevel == countof(gs_Profiler.stack))) 
	{
        MMO_ASSERT(false);
        return;
    }
    if (timer->index < 0) 
	{
        timer->index = gs_Profiler.timerCount;
        gs_Profiler.timers[gs_Profiler.timerCount++] = timer;
        timer->level = gs_Profiler.stackLevel;
    }
    // save parent 
    if (gs_Profiler.stackLevel > 0) 
	{
        PROFILE_TIMER* parent = gs_Profiler.stack[gs_Profiler.stackLevel - 1];
        if (timer->parentIndex == PROFILER_NO_PARENT) 
		{
            timer->parentIndex = parent->index;
            timer->level = gs_Profiler.stackLevel;
        }
        else if (timer->parentIndex != parent->index) 
		{
            timer->parentIndex = PROFILER_MULTI_PARENT;
        }
    }

    gs_Profiler.stack[gs_Profiler.stackLevel++] = timer;
#ifdef WIN32
    QueryPerformanceCounter((LARGE_INTEGER*)&timer->beginTime);
#else
    clock_gettime(CLOCK_MONOTONIC, &timer->beginTime);
#endif // WIN32
}

void EndProfile() 
{
	if (!g_isOpenProfile)
	{
		return;
	}

    if (gs_Profiler.stackLevel == 0) 
	{
        MMO_ASSERT(false && "Not match BeginProfile()");
        return;
    }
    PROFILE_TIMER *timer = gs_Profiler.stack[--gs_Profiler.stackLevel];

    static const long long NonoSecond = 1000000000LL;
#ifdef WIN32
    LARGE_INTEGER endTime;
    QueryPerformanceCounter(&endTime);
    long long diffNanosecond = (endTime.QuadPart - timer->beginTime) * NonoSecond / gs_Frequence.QuadPart;
#else
    timespec endTime;
    clock_gettime(CLOCK_MONOTONIC, &endTime);
    long long diffNanosecond =
        (endTime.tv_sec - timer->beginTime.tv_sec) * NonoSecond +
        (endTime.tv_nsec - timer->beginTime.tv_nsec);
#endif // WIN32

    timer->sampleTime  += diffNanosecond;
    timer->sampleCount += 1;

}

void SetProfileThreadID() 
{
    gs_ProfileThreadID = ThreadId();
}

void BeginProfileWithThreadCheck(PROFILE_TIMER* timer) 
{
    if (gs_ProfileThreadID == ThreadId())
        BeginProfile(timer);
}

void EndProfileWithThreadCheck() 
{
    if (gs_ProfileThreadID == ThreadId())
		EndProfile();
}

void ResetAllProfileTimer() 
{
    for (unsigned i = 0; i < gs_Profiler.timerCount; ++i) 
	{
        auto timer = gs_Profiler.timers[i];
        timer->Clear();
    }
    gs_Profiler.timerCount = 0;
    gs_Profiler.stackLevel = 0;
}

struct CALL_TREE_NODE 
{
    const char* name;
    int parentIndex;
    unsigned  sampleCount;
    long long sampleTime; 

    CALL_TREE_NODE* firstChild;
    CALL_TREE_NODE* nextBrather;
};

static void _AddChildWithSort(CALL_TREE_NODE* parent, CALL_TREE_NODE* child) 
{
    CALL_TREE_NODE *pre = nullptr;
    for (CALL_TREE_NODE* node = parent->firstChild; node; node = node->nextBrather) 
	{
        if (node->sampleTime < child->sampleTime)
			break;
        pre = node;
    }
    if (pre)
	{
        child->nextBrather = pre->nextBrather;
        pre->nextBrather = child;
    }
    else 
	{
        child->nextBrather = parent->firstChild;
        parent->firstChild = child;
    }
 }

static bool _BuildCallTree(CALL_TREE_NODE *head, std::vector<CALL_TREE_NODE> *callTree) 
{
    CALL_TREE_NODE node;
    unsigned timerCount = 0;

    memset(head, 0, sizeof(*head));
    // init
    callTree->reserve(gs_Profiler.timerCount * 2); // must reserve enouth, otherwise pushback() may realloc the memeory, and the pointer to child will be invalid 
    for (unsigned i = 0; i < gs_Profiler.timerCount; ++i) 
	{
        PROFILE_TIMER *timer = gs_Profiler.timers[i];

        node.name  = &(timer->name[0]);
        node.parentIndex = timer->parentIndex;
        node.sampleCount = timer->sampleCount;
        node.sampleTime  = timer->sampleTime;

        node.firstChild = nullptr;
        node.nextBrather = nullptr;
        callTree->push_back(node);
    }

    // build tree
    timerCount = (unsigned)callTree->size();
    CALL_TREE_NODE* nodeArray = callTree->data();
    for (unsigned i = 0; i < timerCount; ++i) 
	{
        CALL_TREE_NODE &node = nodeArray[i];
        if (node.parentIndex >= 0) 
		{
            _AddChildWithSort(&nodeArray[node.parentIndex], &node);
        }
        else {
            _AddChildWithSort(head, &node);
        }
    }
    return true;
}

static void _OutputNode(
    const CALL_TREE_NODE &node, 
    bool showSplitLine,
    long long totalTime, 
    int level,
    std::string *report
	) 
{
    static const int LEVEL_INDENT = 4;
    char line[PROFILER_MAX_STACK_LEVEL * LEVEL_INDENT + PROFILER_MAX_TIMER_NAME_LEN + 128];

    int indentLength = LEVEL_INDENT * level;
    memset(line, ' ', indentLength);
    for (int i = 0; i < level; ++i)
        line[LEVEL_INDENT * i] = '|';

    // split line
    if (showSplitLine) 
	{
        line[indentLength    ] = '|';
        line[indentLength + 1] = '\r';
        line[indentLength + 2] = '\n';
        line[indentLength + 3] = '\0';
        report->append(line);
    }

    char* writePos = line + indentLength;
    int freeSize = countof(line) - indentLength;
    snprintf(
        writePos,
        freeSize,
        "+-[%5.2f%% %6.3fms count=%u]----%s%s\r\n",
        node.sampleTime * 100.f / totalTime,
        node.sampleTime / 1000000.f,
        node.sampleCount,
        node.name,
        (node.parentIndex == PROFILER_MULTI_PARENT) ? "<multi parent>" : ""
    );
    writePos[freeSize - 1] = '\0';
    report->append(line);

    if (report->length() + countof(line) >= (unsigned)LOG_BUFFER_LENGTH) 
	{
        LogInfoFmtPrint("profile:\r\n%s", report->c_str());
        report->clear();
    }
}

static void _OutputCallTree(
    const CALL_TREE_NODE &node, 
    long long totalTime,
    long long minShowTime,
    int level,
    std::string *report
) 
{
    long long childTime = 0;
    bool lastBratherHasChild = false;

    for (CALL_TREE_NODE* child = node.firstChild; child; child = child->nextBrather) 
	{
        if (child->sampleTime < minShowTime)
            continue;

        _OutputNode(*child, lastBratherHasChild, totalTime, level, report);
        childTime += child->sampleTime;

        lastBratherHasChild = false;
        if (child->firstChild) 
		{
            _OutputCallTree(*child, totalTime, minShowTime, level + 1, report);
            lastBratherHasChild = true;
        }
    }            

    long long other = node.sampleTime - childTime;
    if (other > minShowTime) 
	{
        CALL_TREE_NODE otherNode = { 0 };
        otherNode.name = "<other: code not be sample and sampled but too small>";
        otherNode.sampleCount = node.sampleCount;
        otherNode.sampleTime = other;

        _OutputNode(otherNode, lastBratherHasChild, totalTime, level, report);
    }
}

bool OutputTopProfileTimer() 
{
    std::string report;
    CALL_TREE_NODE head;
    std::vector<CALL_TREE_NODE> tree;

    long long totalTime = 0;
    for (unsigned i = 0; i < gs_Profiler.timerCount; ++i) 
	{
        PROFILE_TIMER* timer = gs_Profiler.timers[i];
        if (timer->level == 0)
            totalTime += timer->sampleTime;           
    }
    long long minShowTime = (long long)(totalTime * 0.005f);    

    head.sampleCount = 1;
    head.sampleTime = totalTime;
    _BuildCallTree(&head, &tree); 
    _OutputCallTree(head, totalTime, minShowTime, 0, &report);
	LogAlwaysFmtPrint("profile:\r\n%s", report.c_str());
    return true;
}

static bool _BuildCallTreeByIndex(CALL_TREE_NODE *head, std::vector<CALL_TREE_NODE> *callTree, std::vector<int>& vecIndex) 
{
    CALL_TREE_NODE node;
	unsigned timerCount = 0;

    memset(head, 0, sizeof(*head));
	int count = (int)vecIndex.size();

	std::unordered_map<int, int> reflect;
	std::unordered_map<int, int>::iterator iter;
	std::unordered_map<int, int>::iterator iterEnd;
	int n = 0;

    // init
    callTree->reserve(count * 2); // must reserve enouth, otherwise pushback() may realloc the memeory, and the pointer to child will be invalid 
    for (int i = 0; i < count; ++i) 
	{
		n = vecIndex[i];
		reflect[n] = i;
		iterEnd = reflect.end();

		PROFILE_TIMER *timer = gs_Profiler.timers[n];
        node.sampleCount = timer->sampleCount;
        node.sampleTime  = timer->sampleTime;
        node.name  = &(timer->name[0]);
		
		iter = reflect.find(timer->parentIndex);
		if (iter != iterEnd)
		{
			node.parentIndex = iter->second;
		}
		else
		{
			node.parentIndex = -1;
		}

        node.firstChild = nullptr;
        node.nextBrather = nullptr;
        callTree->push_back(node);
    }

    // build tree
    timerCount = (unsigned)callTree->size();
    CALL_TREE_NODE* nodeArray = callTree->data();

    for (unsigned i = 0; i < timerCount; ++i) 
	{
        CALL_TREE_NODE &node = nodeArray[i];
        if (node.parentIndex >= 0) 
		{
            _AddChildWithSort(&nodeArray[node.parentIndex], &node);
        }
        else {
            _AddChildWithSort(head, &node);
        }
    }
    return true;
}

bool OutputProfileTimer(const char* name, double showTime)
{
    std::string report;
    CALL_TREE_NODE head;
    std::vector<CALL_TREE_NODE> tree;
    static const long long NonoMicSecond = 1000000LL;

	std::set<int> parents;
	std::set<int>::iterator iter;
	std::set<int>::iterator iterEnd;

	bool findTopName = false;
    long long totalTime = 0;

	int beginIndex = 0;
	std::vector<int> vecIndex;

    for (unsigned i = 0; i < gs_Profiler.timerCount; ++i) 
	{
        PROFILE_TIMER* timer = gs_Profiler.timers[i];
		if (!findTopName )
		{
			if (strcmp(name, timer->name) == 0)
			{
				findTopName = true;
				vecIndex.push_back(timer->index);
				beginIndex = timer->index;
				totalTime = timer->sampleTime;

				parents.insert(beginIndex);
				iterEnd = parents.end();
			}
		}
		else 
		{
			iter = parents.find(timer->parentIndex);
			if (iter != iterEnd)
			{
				vecIndex.push_back(timer->index);
				parents.insert(timer->index);
				iterEnd = parents.end();
			}
		}
    }

	long long limitTime = (long long)(showTime * NonoMicSecond);
	if (limitTime >= totalTime)
	{
		return true;
	}

    long long minShowTime = (long long)(totalTime * 0.001f);    
   _BuildCallTreeByIndex(&head, &tree, vecIndex); 
    _OutputCallTree(head, totalTime, minShowTime, 0, &report);
	LogAlwaysFmtPrint("profile:\r\n%s", report.c_str());

	return true;
}

bool OutputProfileTimerByNames(std::unordered_map<std::string, double> names)
{
	std::unordered_map<std::string, double>::iterator iter;
	std::unordered_map<std::string, double>::iterator iterEnd = names.end();
	std::unordered_map<std::string, double> finalProfileNames;

	int curParent = PROFILER_MAX_TIMER_COUNT;

    for (unsigned i = 0; i < gs_Profiler.timerCount; ++i) 
	{
        PROFILE_TIMER* timer = gs_Profiler.timers[i];
		iter = names.find(timer->name);

		if (iter != iterEnd && curParent > timer->parentIndex)
		{
			curParent = timer->parentIndex;
			finalProfileNames.clear();
			finalProfileNames[iter->first] = iter->second;
		}
		else if (iter != iterEnd && curParent == timer->parentIndex)
		{
			finalProfileNames[iter->first] = iter->second;
		}
    }

	iter = finalProfileNames.begin();
	iterEnd = finalProfileNames.end();
	for (; iter != iterEnd; iter++)
	{
		OutputProfileTimer(iter->first.c_str(), iter->second);
	}
	return true;
}
